题解 SRM 563 Div1 500 SpellCards

发表于 | 更新于

$Description$

有$n$张符卡排成一个队列，每张符卡有两个属性，等级$l_{i}$和伤害$d_{i}$。
你可以做任意次操作，每次操作为以下二者之一：

$1$. 把队首的符卡移动到队尾。

$2$. 使用队首的符卡，对敌人造成$d_{i}$点伤害，并丢弃队首的$l_{i}$张符卡（包括你所使用的符卡）。如果队列不足$l_{i}$张符卡那么你不能使用。

求出造成的伤害的总和的最大值。

$1$$\leqslant$$n$$\leqslant$$50,1$$\leqslant$$l_{i}$$\leqslant$$50,1$$\leqslant$$d_{i}$$\leqslant$$10000$

$Solution:$

我们可以把原问题简化成在环上操作，这样第一个操作就被简化掉了

设我们选的集合的点的$l_{i}$为$L_{i}$，注意这里集合内的所有的$L_{i}$是可重的，也就是可以覆盖下一个点，例如下图是合法的。

显然我们只需要满足$\sum L_{i}\leqslant$$n$就行了

我们发现一定有一个点没有覆盖下一个点，证明：如果每个点都覆盖了下一个点，那么整个环一定被完全覆盖了，再加上重叠的部分，$\sum L_{i}$不会$\leqslant$$n$，所有一定有一个点没有覆盖下一个点

那么，我们就可以直接用掉这个点$L_{i}$包含的区间，此时$n-=L_{i}$,剩下的$\sum L_{i}$依然满足$\leqslant$$n$，这个点的上一个点就变成了没有覆盖下一个点的点了，就可以一直删，直到删完。

然后我们发现就是一个裸的背包问题

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int f[60],l[60],d[60];
int main(){
    int n=read();
    for (int i=1;i<=n;++i)l[i]=read();
    for (int i=1;i<=n;++i)d[i]=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            f[j]=max(f[j],f[j-l[i]]+d[i]);
    printf("%d",f[n]);
    return 0;
}